package com.leetcode.partition21;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author `RKC`
 * @date 2022/1/24 10:05
 */
public class LC2045到达目的地的第二短时间 {

    private static final int N = (int) (1e4 + 10), M = 4 * N, INF = 0x3f3f3f3f;
    private static int[] h = new int[N], e = new int[M], ne = new int[M], dist1 = new int[N], dist2 = new int[N];

    private static int n = 0, m = 0, idx = 0;
    //队列中同时维护最短路和次短路
    private static Queue<int[]> queue = new ArrayDeque<>(N);

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]), time = Integer.parseInt(s[2]), change = Integer.parseInt(s[3]);
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            s = reader.readLine().split("\\s+");
            int u = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]);
            edges[i] = new int[]{u, v};
        }
        writer.write(secondMinimum(n, edges, time, change) + "\n");
        writer.flush();
    }

    public static int secondMinimum(int _n, int[][] edges, int time, int change) {
        n = _n;
        m = edges.length;
        idx = 0;
        for (int i = 0; i <= n; i++) h[i] = -1;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            add(u, v);
            add(v, u);
        }
        return bfs(time, change);
    }

    private static int bfs(int time, int change) {
        for (int i = 0; i <= n; i++) dist1[i] = dist2[i] = INF;
        dist1[1] = 0;
        queue.add(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            int u = pair[0], w = pair[1];
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (dist1[v] > w + 1) {
                    dist2[v] = dist1[v];
                    dist1[v] = w + 1;
                    queue.add(new int[]{v, dist1[v]});
                    queue.add(new int[]{v, dist2[v]});
                } else if (dist2[v] > w + 1 && dist1[v] < w + 1) {
                    dist2[v] = w + 1;
                    queue.add(new int[]{v, dist2[v]});
                }
            }
        }
        int answer = 0;
        if (dist2[n] == INF) return -1;
        //因为出发的时候是绿灯，所以改变次数为偶数的时候，在点u上不需要等待；如果改变次数是奇数，在u上需要等待 change-answer%change 的时间
        for (int i = 0; i < dist2[n]; i++) {
            int a = answer / change, r = answer % change;
            int wait = (a & 1) == 0 ? 0 : change - r;
            answer += time + wait;
        }
        return answer;
    }

    private static void add(int u, int v) {
        e[idx] = v;
        ne[idx] = h[u];
        h[u] = idx++;
    }
}
